/*
 * @lc app=leetcode.cn id=13 lang=cpp
 *
 * [13] 罗马数字转整数
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
   public:
    int romanToInt(string s) {
        int result = 0;   // 保存最后的结果
        stack<int> nums;  // 保存待记录的数字

        for (char c : s) {
            // 将字符转化为数字
            int value = 0;
            if (c == 'I') {
                value = 1;
            } else if (c == 'V') {
                value = 5;
            } else if (c == 'X') {
                value = 10;
            } else if (c == 'L') {
                value = 50;
            } else if (c == 'C') {
                value = 100;
            } else if (c == 'D') {
                value = 500;
            } else if (c == 'M') {
                value = 1000;
            } else {
                continue;
            }

            if (nums.empty()) {
                nums.push(value);
                continue;
            } else {
                if (value <= nums.top()) {
                    // 栈顶元素出栈，结果加入该值
                    result += nums.top();
                    nums.pop();
                    nums.push(value);
                } else {
                    // 栈顶元素出栈，结果减去该值
                    result -= nums.top();
                    nums.pop();
                    result += value;
                }
            }
        }

        // 将栈中剩余元素加入结果中
        while (!nums.empty()) {
            result += nums.top();
            nums.pop();
        }

        return result;
    }
};
// @lc code=end
